package org.example.myleet.p1005;

import java.util.Arrays;

public class Solution {

    /**
     * 官方思路：桶排序
     * 利用桶来记录元素出现频数，从而省去快速排序的元素移动时间消耗
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        int base = 100;
        int[] buckets = new int[2 * base + 1];
        for (int num : nums) {
            ++buckets[num + base];
        }
        //记录出现过的最小元素
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i <= 2 * base; ++i) {
            if (i < base && buckets[i] > 0 && k > 0) {
                if (k > buckets[i]) {
                    //k数量足够多，可以反转桶内的所有负数
                    buckets[2 * base - i] += buckets[i];
                    k -= buckets[i];
                    buckets[i] = 0;
                } else {
                    //k数量不足以反转桶内的所有负数，反转一部分
                    buckets[2 * base - i] += k;
                    buckets[i] -= k;
                    k = 0;
                }
            }
            if (buckets[i] > 0 && minValue >= i) {
                minValue = i - base;
            }
        }
        int sum = 0;
        if (k > 0 && (k & 1) == 1) {
            --buckets[base + minValue];
            sum -= minValue;
        }
        for (int i = 0; i <= 2 * base; ++i) {
            if (buckets[i] > 0) {
                sum += (i - base) * buckets[i];
            }
        }
        return sum;
    }

//    public int largestSumAfterKNegations(int[] nums, int k) {
//        Arrays.sort(nums);
//        int minValue = Integer.MAX_VALUE;
//        int minIdx = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            if (nums[i] < 0 && k > 0) {
//                nums[i] = Math.abs(nums[i]);
//                --k;
//            }
//            if (minValue >= nums[i]) {
//                minValue = nums[i];
//                minIdx = i;
//            }
//        }
//        if (k > 0 && (k & 1) == 1) {
//            nums[minIdx] = -nums[minIdx];
//        }
//        int sum = 0;
//        for (int num : nums) {
//            sum += num;
//        }
//        return sum;
//    }
}
